from typing import List


# 枚举法
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        count = 0
        if len(nums) < 3:
            return count
        for i in range(len(nums)-2):
            for j in range(i+1, len(nums)-1):
                for k in range(j+1, len(nums)):
                    if self.isTriangle([nums[i], nums[j], nums[k]]):
                        count += 1
        return count

    def triangleNumber_upgrade(self, nums: List[int]) -> int:
        count = 0
        nums.sort()
        for i in range(len(nums) - 2):
            if nums[i] == 0:
                continue
            k = i + 2
            for j in range(i+1, len(nums) -1):
                while k < len(nums) and nums[i] + nums[j] > nums[k]:
                    k += 1
                count += k - j - 1
        return count

    def isTriangle(self, edges: List) -> bool:
        flag = False
        if edges[0] + edges[1] > edges[2] \
            and edges[0] + edges[2] > edges[1] \
            and edges[1] + edges[2] > edges[0]:
            flag = True
        return flag


if __name__ == '__main__':
    t = [2, 2, 3, 4]
    s = Solution()
    print(s.triangleNumber_upgrade(t))
